package com.jn.algorithm.day006.question18;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 江南大学1033190417
 * @date 2022/4/20 14:00
 */
public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums.length < 4) {
            return result;
        }
        Arrays.sort(nums);
        int length = nums.length;
        for (int first = 0; first < length - 3; first++) {
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            for (int second = first + 1; second < length - 2; second++) {
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                int third = second + 1;
                int forth = length - 1;
                while (third < forth) {
                    int sum = nums[first] + nums[second] + nums[third] + nums[forth];
                    if (sum == target) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[first]);
                        list.add(nums[second]);
                        list.add(nums[third]);
                        list.add(nums[forth]);
                        result.add(list);
                        //左右指针都需要移动
                        int k = third + 1;
                        while (k < forth && nums[k] == nums[third]) {
                            ++k;
                        }
                        third = k;
                    } else if (sum < target) {//移动左指针
                        int k = third + 1;
                        while (k < forth && nums[k] == nums[third]) {
                            ++k;
                        }
                        third = k;
                    } else {
                        int k = forth - 1;
                        while (third > k && nums[k] == nums[forth]) {
                            --k;
                        }
                        forth = k;
                    }
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = new int[]{2, 2, 2, 2, 2};
        int target = 8;
        System.out.println(solution.fourSum(nums, target));
    }
}
